interface HeapInterface<T> {
    list: T[];
    readonly size: number;
    build(list?: T[]): HeapInterface<T>;
    push(...args: T[]): number;
    pop(): T;
    swap(index1: number, index2: number);
    toUp(index: number);
    toDown(index: number);
    getChisIndex(index: number): number[];
    getPIndex(index: number): number;
}

// 大顶堆
class BiggerHeapNumber implements HeapInterface<number> {
    constructor(public list: number[] = []) {
    }
    get size() {
        return this.list.length;
    }
    build(list?: number[]) {
        if (list) {
            this.list = list
        }
        for (let i = Math.floor(this.size); i >= 0; i--) {
            this.toDown(i);
        }
        return this;
    }
    push(...args: number[]): number {
        let size = args.length;
        let len = this.list.push(...args);
        for (let i = 1; i <= size; i++) {
            this.toUp(len - i);
        }
        return len;
    }
    pop(): number {
        let big = this.list[0];
        if (this.size > 1) {
            this.list[0] = this.list[this.size - 1];
        }
        if (this.size > 0) {
            this.list = this.list.slice(0, - 1);
            this.toDown(0);
        }
        return big;
    }
    swap(index1: number, index2: number) {
        let tmp = this.list[index1];
        this.list[index1] = this.list[index2];
        this.list[index2] = tmp;
    }
    toUp(index: number) {
        if (index === 0) {
            return;
        }
        let pIndex = this.getPIndex(index);
        if (this.list[pIndex] < this.list[index]) {
            this.swap(pIndex, index);
            this.toUp(pIndex);
        }
    }
    toDown(index: number) {
        if (index >= this.size) {
            return;
        }
        let [l, r] = this.getChisIndex(index);
        let maxIndex = index;
        if (l && this.list[l] > this.list[maxIndex]) {
            maxIndex = l;
        }
        if (r && this.list[r] > this.list[maxIndex]) {
            maxIndex = r;
        }
        if (maxIndex !== index) {
            this.swap(maxIndex, index);
            this.toDown(maxIndex);
        }
    }
    getChisIndex(index: number) {
        let result: number[] = [];
        let l = 2 * index + 1;
        if (l < this.size) {
            result.push(l);
            let r = 2 * index + 2;
            if (r < this.size) {
                result.push(r);
            }
        }
        return result;
    }
    getPIndex(index: number) {
        let p = Math.ceil(index / 2) - 1;
        return p;
    }
}
// 测试
function main() {
    let list = [2,32,13,453,63,2,2,654,123,653,12,31,124,56,10];
    let h = new BiggerHeapNumber().build(list);
    h.push(0,1,25,6,7,10000);
    while (h.size > 0) {
        console.log(h.pop(), h.size);
    }
}
main();
